链表——在单链表和双向链表中删除倒数第k个结点

Posted on | In ,

题目：分别实现两个函数，分别删除单链表和双链表的倒数第K个节点。
如果链表长度为N，要求时间复杂度达到O(N)，额外空间复杂度达到O(N)。

实现
单链表：

  1. 若单链表长度为空或K小于1，参数无效，直接返回（若设返回参数为Node，则不能直接return，需要加个返回参数，返回头节点，return head）。
  2. 从头到尾遍历链表，每走一步，K的值就减1。当链表走到尾，
    1）如果K >0，则不存在倒数第K个节点；
    2）如果K=0，则头结点就是倒数第K个节点，删除头节点（即直接返回head.next，让第二个节点成为头节点)；
    3）如果k<0，说明倒数第K个节点处在链表中间的某一位置：
  3. 则重头开始走，每走一步，K加1，当K=0的位置，是需要删除的节点的前一个节点。
1
2
3
4
5
6
7
8
//单链表的Node类
public class Node {
	public int data;
	public Node next;
	public Node(int data){
		this.data = data;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class RemoveLastKthNode {
	/**
	 * 删除单链表倒数第K个节点
	 * @param head 链表的头节点
	 * @param k 倒数第k个元素
	 * @return 头节点
	 */
	public static Node removeLastKthNode1(Node head, int k) {
		if (head == null || k < 1) {
			return head;
		}
		Node current = head;
		k--;
		while(current.next != null) {
			k--;
			current = current.next;
		}
		if (k == 0) {
			head = head.next;
		}
		if (k < 0) {
			current = head;
			while(++k != 0) {
				current = current.next;
			}
			/*同义current = head;
			k++;
			while (k != 0) {
				current = current.next;
				k++;
			}*/
			current.next = current.next.next;
		}
		return head; //由于最终都需要返回head，不能使用if else，它只会执行一处条件语句
	}
}

另一种方法：

  1. 设置快慢指针，快指针比慢指针先走k步。
  2. 当快指针走到最后一个节点，慢指针指向要删除节点的前一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 设置快指针和慢指针，快指针比慢指针多走k步，当快指针走到末尾的null,慢指针走到倒数第k个节点
 */
public static Node removeLastKthNode3(Node head, int k) {
	if (head == null || k < 1) {
		return null;
	}
	Node slow = head;
	Node fast = head;
	for (int i = 0; i <= k; i++) {
		fast = fast.next;
	}
	while (fast != null) {
		fast = fast.next;
		slow = slow.next; //此时定位到要删除节点的前一个节点
	}
	Node deleteNode = slow.next;
	slow.next = slow.next.next;
	return deleteNode;
}

双链表：
与单链表的实现类似，只不过它的Node类中多了前向指针。

1
2
3
4
5
6
7
8
9
//双链表的Node类
public class DoubleNode {
	public int data;
	public DoubleNode previous;
	public DoubleNode next;
	public DoubleNode(int data) {
		this.data = data;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 删除双（向）链表倒数第K个节点
 * @param head 链表的头节点
 * @param k 倒数第k个元素
 * @return 头节点
 */
public static DoubleNode removeLastKthNode2(DoubleNode head, int k) {
	if (head == null || k < 1) {
		return head;
	}
	DoubleNode current = head;
	k--;
	while (current.next != null) {
		k--;
		current = current.next;
	}
	if (k == 0) {
		head = head.next;
		head.previous = null;
	}
	if (k < 0) {
		current = head;
		while(++k != 0) {
			current = current.next;
		}
		DoubleNode newNode = current.next.next;
		current.next = newNode;
		//注意要考虑前向指针的指向，为了方便，所以前面两行写成那样，
		//其实与current.next= current.next.next;的意义相同
		if (newNode != null) { 
			newNode.previous = current;
		}
	}
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Test
public static void main(String[] args) {
	Node head1 = new Node(1); 
	Node node1 = new Node(2);
	Node node2 = new Node(3);
	Node node3 = new Node(4);
	head1.next = node1;
	node1.next = node2;
	node2.next = node3;
	DoubleNode head2 = new DoubleNode(4); 
	DoubleNode node4 = new DoubleNode(3);
	DoubleNode node5 = new DoubleNode(2);
	DoubleNode node6 = new DoubleNode(1);
	head2.next = node4;
	node4.next = node5;
	node5.next = node6;
	System.out.println(removeLastKthNode1(head1, 0).data); //返回头节点
	System.out.println(removeLastKthNode2(head2, 0).data); //返回头节点
}